// 左节点 --> 右节点--> 根节点
// 解法1，递归
function postOrderTraversal(root: TreeNode | null): any[] {
    if (!root) {
        return []
    }
    // 获取节点数据
    const res = []
    // 执行遍历：左节点--> 根节点 --> 右节点
    const postOrder =(node: TreeNode | null) =>{
        if(!node){
            return 
        }
        postOrder(node.left)
        postOrder(node.right)
        res.push(node.val)
    }
    postOrder(root)
    return res
}

// 解法2 迭代法
function postOrderTraversal(root: TreeNode | null): any[] {
    if (!root) {
        return [];
    }
    // 获取节点数据
    const res = [];
    let stack:TreeNode[] = [];
    // 存储最终的节点读取顺序
    let stack2:TreeNode[] = []
    stack.push(root)
    while(stack.length){
        const node:TreeNode = stack.pop();
        stack2.push(node)
        // 这里先放left进入，后方right，
        // 因为前面两句代码会把node放到最下面，right放到下中间，left放到面
        if(node.left){
            stack.push(node.left);
        }
        if(node.right){
            stack.push(node.right);
        }
    }
    while(stack2.length){
        res.push(stack2.pop().val)
    }
    return res
}
// 解法3，mirris, 没太懂这个逻辑
function postorderTraversal3(root: TreeNode | null): number[] {
    if(!root){
        return [];
    }
    let head = root;
    const res = [];
    // 前驱节点
    let predecessor:TreeNode = null;
    const postMorrisReverseList = (head: TreeNode) =>{

        let cur:TreeNode = head;
        let pre:TreeNode = null;
        while(cur){
            const next:TreeNode = cur.right;
            cur.right = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
    const postMorrisResult = (head: TreeNode) =>{
        const reverseList:TreeNode = postMorrisReverseList(head);
        let cur:TreeNode = reverseList;
        while(cur){
            res.push(cur.val);
            cur = cur.right;
        }
    }
    while(root){
        predecessor = root.left;
        // 如果当前节点有左子树
        if(predecessor){
            // 找到左子树的最右边的节点
            while(predecessor.right && predecessor.right !== root){
                predecessor = predecessor.right
            }
            // 如果最右边的节点的right没有被标记过，就把root赋值给前驱节点的right
            // 同时跳过当前依次循环
            // 一个节点第一次遍历的时候是没有，right的
            if(!predecessor.right){
                predecessor.right = root;
                root = root.left;
                continue;
            // 如果前驱节点被标记过了，就取消标记，
            // 并且读取数据
            // 第二次遍历该节点是，有了right，开始读取数据
            }else{
                // 同时取消索引。同时经过后端的root = root.right,去到了右子树。
                predecessor.right = null;
                postMorrisResult(root.left)
            }
        }
        // 如果遍历的节点没有了左子树，
        // 就可以获取当前节点的右索引，这里右边的节点是它所在左子树的父节点。
        root = root.right;
    }
    postMorrisResult(head)
    return res
};